/*
 * Sort.cpp
 *
 *  Created on: 2014年5月6日
 *      Author: rock
 */

#include "Sort.h"
#include <iostream>
using namespace std;

//From small to large.
//需要移动数组, 因为插入了,后面的就要不断的移动.
/*
 * 直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，
 * 开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有
 * 序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
 *
 * 这里面采用了分治策略, 把数组分为两部分. 第一个是有序的序列, 其他的是无序的序列.
 */
void insertSort(int* array, int arrayLen)
{
	int temp = 0;
	int index = 0;
	for (int i = 1; i < arrayLen; i++) //取无序表中的n-1个元素. 把他们插入到有序表中.
	{
		temp = array[i];
		//从后向前遍历无序列表, 如果当前元素大于无序列表的第一个并且没有到头,那么
		//所以无序的这第一个元素要继续往前移,当前元素向后移一个空出无序元素的位置.
		for (index = i - 1; index >= 0 && temp < array[index]; index--) //遍历有序表的迭代.
		{
			array[index + 1] = array[index];
		}
		//把无序列表放到正确的位置上.
		array[index + 1] = temp;
	}

}

//遍历每一个位置, 与后面的进行判断, 如果小于则进去交换.
//踩在一点上, 遍历后面的点进行判断. 不断的选择最小的一个.
void selectSort(int * array, int arrayLen)
{
	int swapVal = 0;

	for (int i = 0; i < arrayLen; i++)
	{
		for (int j = i + 1; j < arrayLen; j++)
		{
			if (array[j] < array[i])
			{
				swapVal = array[j];
				array[j] = array[i];
				array[i] = swapVal;
			}
		}
	}
}

/*
 * 冒泡排序,其实是把最大的不断放到最后面.
 * 经过N轮的比较，每次相邻的两两比较，然后把较大的下沉。
 * 所以第一轮最大的下沉到最底下，第二输第二大的下沉到次底。
 */
void bubleSort(int * array, int arrayLen)
{
	int swapVal = 0;

	//第一回合，把最大的放在最后，第二回合把第二大的放在最后。
	//所以需要数组长度个回合.
	for (int i = 0; i < arrayLen; i++)
	{
		//前多少个不是最大的,两两比较,把最大的沉底.
		for (int j = 0; j < arrayLen - i - 1; j++) //把最大的放到最后，因为两个相邻的不断在交换。
		{
			if (array[j] > array[j + 1])
			{
				swapVal = array[j];
				array[j] = array[j + 1];
				array[j + 1] = swapVal;
			}
		}

	}
}

/*
 *快速排序
 *分治策略的集中体现.
 *划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
 *将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
 */

void quickSort(int * array, int startIndex, int endIndex)
{
	if (endIndex - startIndex <= 0)
	{
		//cout << "Parameter error" << endl;
		return;
	}

	//这个base实际像是被挖空的位置, 在最后一步把合适的值填上去.
	int base = array[startIndex];
	int i = startIndex, j = endIndex;

	while(i < j)
	{
		while(i < j && array[j] >= base)
			j--;
		//j位置是第一个<base的位置.

		//把j位置的数给当前空位i. j位置空下来. i已经是小于Base, 所以i主动+1
		if(i < j)
		    array[i++] = array[j];

		while(i < j && array[i] < base) // 从左向右找第一个大于等于x的数
		    i++;
		//i位置是第一个>=base的位置.

		//把i当前位置大的这个数给空下来的j位置. i被挖空.
		if(i < j)
			array[j--] = array[i];
	}

	array[i] = base;

	quickSort(array, startIndex, i - 1); // 递归调用
	quickSort(array, i + 1, endIndex);

}


/*计数排序算法*/
void CounterSort(string str, string &sort_str)  
{  
	// 辅助计数数组  
	int help[26] = {0};  

	// help[index]存放了等于index + 'A'的元素个数  
	for (size_t i = 0; i < str.length(); i++)
	{  
		int index = str[i] - 'A';  
		help[index]++;  
	}  

	// 求出每个元素对应的最终位置  
	for (int j = 1; j < 26; j++)  
		help[j] += help[j-1];  

	// 把每个元素放到其对应的最终位置  
	for (int k = str.length() - 1; k >= 0; k--)  
	{  
		int index = str[k] - 'A';  
		int pos = help[index] - 1;  
		sort_str[pos] = str[k];  
		help[index]--;  
	}  
}  

void CounterSort(const char * str, char * sort_str)
{
	// 辅助计数数组  
	int help[26] = {0};  

	const int LEN = strlen(str);
	// help[index]存放了等于index + 'A'的元素个数  
	for (int i = 0; i < LEN; i++)  
	{  
		int index = str[i] - 'A';  
		help[index]++;  
	}  

	// 求出每个元素对应的最终位置  
	for (int j = 1; j < 26; j++)  
		help[j] += help[j-1];  

	// 把每个元素放到其对应的最终位置  
	for (int k = LEN - 1; k >= 0; k--)  
	{  
		int index = str[k] - 'A';  
		int pos = help[index] - 1;  
		sort_str[pos] = str[k];  
		help[index]--;  
	}  
}

